home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1994 November / macformat-018.iso / Utility Spectacular / Developer / Marlais 0.3.1 / gc4.1-mac / src / mark.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-26  |  28.9 KB  |  1,051 lines  |  [TEXT/R*ch]
  1.  
  2. /*
  3.  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  4.  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
  5.  *
  6.  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  7.  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  8.  *
  9.  * Permission is hereby granted to use or copy this program
  10.  * for any purpose,  provided the above notices are retained on all copies.
  11.  * Permission to modify the code and to distribute modified code is granted,
  12.  * provided the above notices are retained, and a notice that the code was
  13.  * modified is included with the above copyright notice.
  14.  *
  15.  */
  16.  
  17.  
  18. # include <stdio.h>
  19. # include "gc_priv.h"
  20. # include "gc_mark.h"
  21.  
  22. /* We put this here to minimize the risk of inlining. */
  23. /*VARARGS*/
  24. void GC_noop() {}
  25.  
  26. mark_proc GC_mark_procs[MAX_MARK_PROCS] = {0};
  27. word GC_n_mark_procs = 0;
  28.  
  29. /* Initialize GC_obj_kinds properly and standard free lists properly.      */
  30. /* This must be done statically since they may be accessed before         */
  31. /* GC_init is called.                                                    */
  32.  
  33. /* PCB -- this is no longer true, GC_init must be called to use the collector. */
  34.  
  35. /* It's done here, since we need to deal with mark descriptors.            */
  36.  
  37. struct obj_kind GC_obj_kinds[MAXOBJKINDS] = {
  38. /* PTRFREE */ { 0, 0,    /* initialized below. */
  39.         0 | DS_LENGTH, FALSE, FALSE },
  40. /* NORMAL  */ { 0, 0,    /* initialized below. */
  41. #        ifdef ADD_BYTE_AT_END
  42.         (word)(WORDS_TO_BYTES(-1)) | DS_LENGTH,
  43. #        else
  44.         0 | DS_LENGTH,
  45. #        endif
  46.         TRUE /* add length to descr */, TRUE },
  47. /* UNCOLLECTABLE */
  48.           { 0, 0,        /* initialized below. */
  49.         0 | DS_LENGTH, TRUE /* add length to descr */, TRUE },
  50. # ifdef STUBBORN_ALLOC
  51. /*STUBBORN*/ { 0, 0,    /* initialized below. */
  52.         0 | DS_LENGTH, TRUE /* add length to descr */, TRUE },
  53. # endif
  54. };
  55.  
  56. /* PCB - had to change these to runtime initialization since no longer static. */
  57.  
  58. void GC_init_mark()
  59. {
  60.     GC_obj_kinds[PTRFREE].ok_freelist = &GC_aobjfreelist[0];
  61.     GC_obj_kinds[PTRFREE].ok_reclaim_list = &GC_areclaim_list[0];
  62.  
  63.     GC_obj_kinds[NORMAL].ok_freelist = &GC_objfreelist[0];
  64.     GC_obj_kinds[NORMAL].ok_reclaim_list = &GC_reclaim_list[0];
  65.  
  66.     GC_obj_kinds[UNCOLLECTABLE].ok_freelist = &GC_uobjfreelist[0];
  67.     GC_obj_kinds[UNCOLLECTABLE].ok_reclaim_list = &GC_ureclaim_list[0];
  68.  
  69. # ifdef STUBBORN_ALLOC
  70.     GC_obj_kinds[STUBBORN].ok_freelist = &GC_sobjfreelist[0];
  71.     GC_obj_kinds[STUBBORN].ok_reclaim_list = &GC_sreclaim_list[0];
  72. #endif
  73. }
  74.  
  75.  
  76. # ifdef STUBBORN_ALLOC
  77.   int GC_n_kinds = 4;
  78. # else
  79.   int GC_n_kinds = 3;
  80. # endif
  81.  
  82.  
  83. # define INITIAL_MARK_STACK_SIZE (1*HBLKSIZE)
  84.         /* INITIAL_MARK_STACK_SIZE * sizeof(mse) should be a     */
  85.         /* multiple of HBLKSIZE.                */
  86.  
  87. /*
  88.  * Limits of stack for GC_mark routine.
  89.  * All ranges between GC_mark_stack(incl.) and GC_mark_stack_top(incl.) still
  90.  * need to be marked from.
  91.  */
  92.  
  93. word GC_n_rescuing_pages;    /* Number of dirty pages we marked from */
  94.                 /* excludes ptrfree pages, etc.        */
  95.  
  96. mse * GC_mark_stack;
  97.  
  98. word GC_mark_stack_size = 0;
  99.  
  100. mse * GC_mark_stack_top;
  101.  
  102. static struct hblk * scan_ptr;
  103.  
  104. mark_state_t GC_mark_state = MS_NONE;
  105.  
  106. bool GC_mark_stack_too_small = FALSE;
  107.  
  108. bool GC_objects_are_marked = FALSE;    /* Are there collectable marked    */
  109.                     /* objects in the heap?        */
  110.  
  111. bool GC_collection_in_progress()
  112. {
  113.     return(GC_mark_state != MS_NONE);
  114. }
  115.  
  116. /* clear all mark bits in the header */
  117. void GC_clear_hdr_marks(hhdr)
  118. register hdr * hhdr;
  119. {
  120.     BZERO(hhdr -> hb_marks, MARK_BITS_SZ*sizeof(word));
  121. }
  122.  
  123. /*
  124.  * Clear all mark bits associated with block h.
  125.  */
  126. /*ARGSUSED*/
  127. static void clear_marks_for_block(h, dummy)
  128. struct hblk *h;
  129. word dummy;
  130. {
  131.     register hdr * hhdr = HDR(h);
  132.     
  133.     if (hhdr -> hb_obj_kind == UNCOLLECTABLE) return;
  134.         /* Mark bit for these is cleared only once the object is     */
  135.         /* explicitly deallocated.  This either frees the block, or    */
  136.         /* the bit is cleared once the object is on the free list.    */
  137.     GC_clear_hdr_marks(hhdr);
  138. }
  139.  
  140. /* Slow but general routines for setting/clearing/asking about mark bits */
  141. void GC_set_mark_bit(p)
  142. ptr_t p;
  143. {
  144.     register struct hblk *h = HBLKPTR(p);
  145.     register hdr * hhdr = HDR(h);
  146.     register int word_no = (word *)p - (word *)h;
  147.     
  148.     set_mark_bit_from_hdr(hhdr, word_no);
  149. }
  150.  
  151. void GC_clear_mark_bit(p)
  152. ptr_t p;
  153. {
  154.     register struct hblk *h = HBLKPTR(p);
  155.     register hdr * hhdr = HDR(h);
  156.     register int word_no = (word *)p - (word *)h;
  157.     
  158.     clear_mark_bit_from_hdr(hhdr, word_no);
  159. }
  160.  
  161. bool GC_is_marked(p)
  162. ptr_t p;
  163. {
  164.     register struct hblk *h = HBLKPTR(p);
  165.     register hdr * hhdr = HDR(h);
  166.     register int word_no = (word *)p - (word *)h;
  167.     
  168.     return(mark_bit_from_hdr(hhdr, word_no));
  169. }
  170.  
  171.  
  172. /*
  173.  * Clear mark bits in all allocated heap blocks.  This invalidates
  174.  * the marker invariant, and sets GC_mark_state to reflect this.
  175.  * (This implicitly starts marking to reestablish the
  176.  */
  177. void GC_clear_marks()
  178. {
  179.     GC_apply_to_all_blocks(clear_marks_for_block, (word)0);
  180.     GC_objects_are_marked = FALSE;
  181.     GC_mark_state = MS_INVALID;
  182.     scan_ptr = 0;
  183. #   ifdef GATHERSTATS
  184.     /* Counters reflect currently marked objects: reset here */
  185.         GC_composite_in_use = 0;
  186.         GC_atomic_in_use = 0;
  187. #   endif
  188.  
  189. }
  190.  
  191. /* Initiate full marking.    */
  192. void GC_initiate_full()
  193. {
  194. #   ifdef PRINTSTATS
  195.     GC_printf2("***>Full mark for collection %lu after %ld allocd bytes\n",
  196.           (unsigned long) GC_gc_no+1,
  197.              (long)WORDS_TO_BYTES(GC_words_allocd));
  198. #   endif
  199.     GC_promote_black_lists();
  200.     GC_reclaim_or_delete_all();
  201.     GC_clear_marks();
  202.     GC_read_dirty();
  203. #   ifdef STUBBORN_ALLOC
  204.         GC_read_changed();
  205. #   endif
  206. #   ifdef CHECKSUMS
  207.     {
  208.         extern void GC_check_dirty();
  209.         
  210.         GC_check_dirty();
  211.     }
  212. #   endif
  213. #   ifdef GATHERSTATS
  214.     GC_n_rescuing_pages = 0;
  215. #   endif
  216. }
  217.  
  218. /* Initiate partial marking.    */
  219. /*ARGSUSED*/
  220. void GC_initiate_partial()
  221. {
  222.     if (GC_dirty_maintained) GC_read_dirty();
  223. #   ifdef STUBBORN_ALLOC
  224.         GC_read_changed();
  225. #   endif
  226. #   ifdef CHECKSUMS
  227.     {
  228.         extern void GC_check_dirty();
  229.         
  230.         if (GC_dirty_maintained) GC_check_dirty();
  231.     }
  232. #   endif
  233. #   ifdef GATHERSTATS
  234.     GC_n_rescuing_pages = 0;
  235. #   endif
  236.     if (GC_mark_state == MS_NONE) {
  237.         GC_mark_state = MS_PUSH_RESCUERS;
  238.     } else if (GC_mark_state != MS_INVALID) {
  239.         ABORT("unexpected state");
  240.     } /* else this is really a full collection, and mark    */
  241.       /* bits are invalid.                    */
  242.     scan_ptr = 0;
  243. }
  244.  
  245.  
  246. static void alloc_mark_stack();
  247.  
  248. /* Perform a small amount of marking.            */
  249. /* We try to touch roughly a page of memory.        */
  250. /* Return TRUE if we just finished a mark phase.    */
  251. bool GC_mark_some()
  252. {
  253.     switch(GC_mark_state) {
  254.         case MS_NONE:
  255.             return(FALSE);
  256.             
  257.         case MS_PUSH_RESCUERS:
  258.             if (GC_mark_stack_top
  259.                 >= GC_mark_stack + INITIAL_MARK_STACK_SIZE/4) {
  260.                 GC_mark_from_mark_stack();
  261.                 return(FALSE);
  262.             } else {
  263.                 scan_ptr = GC_push_next_marked_dirty(scan_ptr);
  264.                 if (scan_ptr == 0) {
  265. #            ifdef PRINTSTATS
  266.             GC_printf1("Marked from %lu dirty pages\n",
  267.                    (unsigned long)GC_n_rescuing_pages);
  268. #            endif
  269.                     GC_push_roots(FALSE);
  270.                     GC_objects_are_marked = TRUE;
  271.                     if (GC_mark_state != MS_INVALID) {
  272.                         GC_mark_state = MS_ROOTS_PUSHED;
  273.                     }
  274.                 }
  275.             }
  276.             return(FALSE);
  277.         
  278.         case MS_PUSH_UNCOLLECTABLE:
  279.             if (GC_mark_stack_top
  280.                 >= GC_mark_stack + INITIAL_MARK_STACK_SIZE/4) {
  281.                 GC_mark_from_mark_stack();
  282.                 return(FALSE);
  283.             } else {
  284.                 scan_ptr = GC_push_next_marked_uncollectable(scan_ptr);
  285.                 if (scan_ptr == 0) {
  286.                     GC_push_roots(TRUE);
  287.                     GC_objects_are_marked = TRUE;
  288.                     if (GC_mark_state != MS_INVALID) {
  289.                         GC_mark_state = MS_ROOTS_PUSHED;
  290.                     }
  291.                 }
  292.             }
  293.             return(FALSE);
  294.         
  295.         case MS_ROOTS_PUSHED:
  296.             if (GC_mark_stack_top >= GC_mark_stack) {
  297.                 GC_mark_from_mark_stack();
  298.                 return(FALSE);
  299.             } else {
  300.                 GC_mark_state = MS_NONE;
  301.                 if (GC_mark_stack_too_small) {
  302.                     alloc_mark_stack(2*GC_mark_stack_size);
  303.                 }
  304.                 return(TRUE);
  305.             }
  306.             
  307.         case MS_INVALID:
  308.         case MS_PARTIALLY_INVALID:
  309.         if (!GC_objects_are_marked) {
  310.         GC_mark_state = MS_PUSH_UNCOLLECTABLE;
  311.         return(FALSE);
  312.         }
  313.             if (GC_mark_stack_top >= GC_mark_stack) {
  314.                 GC_mark_from_mark_stack();
  315.                 return(FALSE);
  316.             }
  317.             if (scan_ptr == 0
  318.                 && (GC_mark_state == MS_INVALID || GC_mark_stack_too_small)) {
  319.                 alloc_mark_stack(2*GC_mark_stack_size);
  320.         GC_mark_state = MS_PARTIALLY_INVALID;
  321.             }
  322.             scan_ptr = GC_push_next_marked(scan_ptr);
  323.             if (scan_ptr == 0 && GC_mark_state == MS_PARTIALLY_INVALID) {
  324.                 GC_push_roots(TRUE);
  325.                 GC_objects_are_marked = TRUE;
  326.                 if (GC_mark_state != MS_INVALID) {
  327.                     GC_mark_state = MS_ROOTS_PUSHED;
  328.                 }
  329.             }
  330.             return(FALSE);
  331.         default:
  332.             ABORT("GC_mark_some: bad state");
  333.             return(FALSE);
  334.     }
  335. }
  336.  
  337.  
  338. bool GC_mark_stack_empty()
  339. {
  340.     return(GC_mark_stack_top < GC_mark_stack);
  341. }    
  342.  
  343. #ifdef PROF_MARKER
  344.     word GC_prof_array[10];
  345. #   define PROF(n) GC_prof_array[n]++
  346. #else
  347. #   define PROF(n)
  348. #endif
  349.  
  350. /* Given a pointer to someplace other than a small object page or the    */
  351. /* first page of a large object, return a pointer either to the        */
  352. /* start of the large object or NIL.                    */
  353. /* In the latter case black list the address current.            */
  354. /* Returns NIL without black listing if current points to a block    */
  355. /* with IGNORE_OFF_PAGE set.                        */
  356. /*ARGSUSED*/
  357. word GC_find_start(current, hhdr)
  358. register word current;
  359. register hdr * hhdr;
  360. {
  361. #   ifdef ALL_INTERIOR_POINTERS
  362.     if (hhdr != 0) {
  363.         register word orig = current;
  364.         
  365.         current = (word)HBLKPTR(current) + HDR_BYTES;
  366.         do {
  367.           current = current - HBLKSIZE*(int)hhdr;
  368.           hhdr = HDR(current);
  369.         } while(IS_FORWARDING_ADDR_OR_NIL(hhdr));
  370.         /* current points to the start of the large object */
  371.         if (hhdr -> hb_flags & IGNORE_OFF_PAGE) return(0);
  372.         if ((word *)orig - (word *)current
  373.              >= (ptrdiff_t)(hhdr->hb_sz)) {
  374.             /* Pointer past the end of the block */
  375.             GC_ADD_TO_BLACK_LIST_NORMAL(orig);
  376.             return(0);
  377.         }
  378.         return(current);
  379.     } else {
  380.         GC_ADD_TO_BLACK_LIST_NORMAL(current);
  381.         return(0);
  382.         }
  383. #   else
  384.         GC_ADD_TO_BLACK_LIST_NORMAL(current);
  385.         return(0);
  386. #   endif
  387. }
  388.  
  389. mse * GC_signal_mark_stack_overflow(msp)
  390. mse * msp;
  391. {
  392.     GC_mark_state = MS_INVALID;
  393. #   ifdef PRINTSTATS
  394.     GC_printf1("Mark stack overflow; current size = %lu entries\n",
  395.                 GC_mark_stack_size);
  396. #    endif
  397.      return(msp-INITIAL_MARK_STACK_SIZE/8);
  398. }
  399.  
  400.  
  401. /*
  402.  * Mark objects pointed to by the regions described by
  403.  * mark stack entries between GC_mark_stack and GC_mark_stack_top,
  404.  * inclusive.  Assumes the upper limit of a mark stack entry
  405.  * is never 0.  A mark stack entry never has size 0.
  406.  * We try to traverse on the order of a hblk of memory before we return.
  407.  * Caller is responsible for calling this until the mark stack is empty.
  408.  */
  409. void GC_mark_from_mark_stack()
  410. {
  411.   mse * GC_mark_stack_reg = GC_mark_stack;
  412.   mse * GC_mark_stack_top_reg = GC_mark_stack_top;
  413.   mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]);
  414.   int credit = HBLKSIZE;    /* Remaining credit for marking work    */
  415.   register word * current_p;    /* Pointer to current candidate ptr.    */
  416.   register word current;    /* Candidate pointer.            */
  417.   register word * limit;    /* (Incl) limit of current candidate     */
  418.                   /* range                */
  419.   register word descr;
  420.   register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
  421.   register ptr_t least_ha = GC_least_plausible_heap_addr;
  422. # define SPLIT_RANGE_WORDS 128  /* Must be power of 2.        */
  423.  
  424.   GC_objects_are_marked = TRUE;
  425. # ifdef OS2 /* Use untweaked version to circumvent compiler problem */
  426.   while (GC_mark_stack_top_reg >= GC_mark_stack_reg && credit >= 0) {
  427. # else
  428.   while ((((ptr_t)GC_mark_stack_top_reg - (ptr_t)GC_mark_stack_reg) | credit)
  429.       >= 0) {
  430. # endif
  431.     current_p = GC_mark_stack_top_reg -> mse_start;
  432.     descr = GC_mark_stack_top_reg -> mse_descr;
  433.   retry:  
  434.     if (descr & ((~(WORDS_TO_BYTES(SPLIT_RANGE_WORDS) - 1)) | DS_TAGS)) {
  435.       word tag = descr & DS_TAGS;
  436.       
  437.       switch(tag) {
  438.         case DS_LENGTH:
  439.           /* Large length.                            */
  440.           /* Process part of the range to avoid pushing too much on the    */
  441.           /* stack.                            */
  442.           GC_mark_stack_top_reg -> mse_start =
  443.              limit = current_p + SPLIT_RANGE_WORDS-1;
  444.           GC_mark_stack_top_reg -> mse_descr -=
  445.                   WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
  446.           /* Make sure that pointers overlapping the two ranges are    */
  447.           /* considered.                         */
  448.           limit += sizeof(word) - ALIGNMENT;
  449.           break;
  450.         case DS_BITMAP:
  451.           GC_mark_stack_top_reg--;
  452.           descr &= ~DS_TAGS;
  453.           credit -= WORDS_TO_BYTES(WORDSZ/2); /* guess */
  454.           while (descr != 0) {
  455.             if ((signed_word)descr < 0) {
  456.               current = *current_p++;
  457.               descr <<= 1;
  458.               if ((ptr_t)current < least_ha) continue;
  459.               if ((ptr_t)current >= greatest_ha) continue;
  460.               PUSH_CONTENTS(current, GC_mark_stack_top_reg, mark_stack_limit);
  461.             } else {
  462.               descr <<= 1;
  463.               current_p++;
  464.             }
  465.           }
  466.           continue;
  467.         case DS_PROC:
  468.           GC_mark_stack_top_reg--;
  469.           credit -= PROC_BYTES;
  470.           GC_mark_stack_top_reg =
  471.               (*PROC(descr))
  472.                       (current_p, GC_mark_stack_top_reg,
  473.                       mark_stack_limit, ENV(descr));
  474.           continue;
  475.         case DS_PER_OBJECT:
  476.           descr = *(word *)((ptr_t)current_p + descr - tag);
  477.           goto retry;
  478.       }
  479.     } else {
  480.       GC_mark_stack_top_reg--;
  481.       limit = (word *)(((ptr_t)current_p) + (word)descr);
  482.     }
  483.     /* The simple case in which we're scanning a range.    */
  484.     credit -= (ptr_t)limit - (ptr_t)current_p;
  485.     limit -= 1;
  486.     while (current_p <= limit) {
  487.       current = *current_p;
  488.       current_p = (word *)((char *)current_p + ALIGNMENT);
  489.       if ((ptr_t)current < least_ha) continue;
  490.       if ((ptr_t)current >= greatest_ha) continue;
  491.       PUSH_CONTENTS(current, GC_mark_stack_top_reg, mark_stack_limit);
  492.     }
  493.   }
  494.   GC_mark_stack_top = GC_mark_stack_top_reg;
  495. }
  496.  
  497. /* Allocate or reallocate space for mark stack of size s words  */
  498. /* May silently fail.                        */
  499. static void alloc_mark_stack(n)
  500. word n;
  501. {
  502.     mse * new_stack = (mse *)GC_scratch_alloc(n * sizeof(struct ms_entry));
  503.     
  504.     GC_mark_stack_too_small = FALSE;
  505.     if (GC_mark_stack_size != 0) {
  506.         if (new_stack != 0) {
  507.           word displ = HBLKDISPL(GC_mark_stack);
  508.           word size = GC_mark_stack_size * sizeof(struct ms_entry);
  509.           
  510.           /* Recycle old space */
  511.             if (displ == 0) {
  512.               GC_add_to_heap((struct hblk *)GC_mark_stack, size);
  513.         } else {
  514.           GC_add_to_heap((struct hblk *)
  515.                       ((word)GC_mark_stack - displ + HBLKSIZE),
  516.                        size - HBLKSIZE);
  517.         }
  518.           GC_mark_stack = new_stack;
  519.           GC_mark_stack_size = n;
  520. #      ifdef PRINTSTATS
  521.           GC_printf1("Grew mark stack to %lu frames\n",
  522.                  (unsigned long) GC_mark_stack_size);
  523. #      endif
  524.         } else {
  525. #      ifdef PRINTSTATS
  526.           GC_printf1("Failed to grow mark stack to %lu frames\n",
  527.                  (unsigned long) n);
  528. #      endif
  529.         }
  530.     } else {
  531.         if (new_stack == 0) {
  532.             GC_err_printf0("No space for mark stack\n");
  533.             EXIT();
  534.         }
  535.         GC_mark_stack = new_stack;
  536.         GC_mark_stack_size = n;
  537.     }
  538.     GC_mark_stack_top = GC_mark_stack-1;
  539. }
  540.  
  541. void GC_mark_init()
  542. {
  543.     alloc_mark_stack(INITIAL_MARK_STACK_SIZE);
  544. }
  545.  
  546. /*
  547.  * Push all locations between b and t onto the mark stack.
  548.  * b is the first location to be checked. t is one past the last
  549.  * location to be checked.
  550.  * Should only be used if there is no possibility of mark stack
  551.  * overflow.
  552.  */
  553. void GC_push_all(bottom, top)
  554. ptr_t bottom;
  555. ptr_t top;
  556. {
  557.     register word length;
  558.     
  559.     bottom = (ptr_t)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
  560.     top = (ptr_t)(((word) top) & ~(ALIGNMENT-1));
  561.     if (top == 0 || bottom == top) return;
  562.     GC_mark_stack_top++;
  563.     if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) {
  564.     ABORT("unexpected mark stack overflow");
  565.     }
  566.     length = top - bottom;
  567. #   if DS_TAGS > ALIGNMENT - 1
  568.     length += DS_TAGS;
  569.     length &= ~DS_TAGS;
  570. #   endif
  571.     GC_mark_stack_top -> mse_start = (word *)bottom;
  572.     GC_mark_stack_top -> mse_descr = length;
  573. }
  574.  
  575. /*
  576.  * Analogous to the above, but push only those pages that may have been
  577.  * dirtied.  A block h is assumed dirty if dirty_fn(h) != 0.
  578.  * We use push_fn to actually push the block.
  579.  * Will not overflow mark stack if push_fn pushes a small fixed number
  580.  * of entries.  (This is invoked only if push_fn pushes a single entry,
  581.  * or if it marks each object before pushing it, thus ensuring progress
  582.  * in the event of a stack overflow.)
  583.  */
  584. void GC_push_dirty(bottom, top, dirty_fn, push_fn)
  585. ptr_t bottom;
  586. ptr_t top;
  587. int (*dirty_fn)(/* struct hblk * h */);
  588. void (*push_fn)(/* ptr_t bottom, ptr_t top */);
  589. {
  590.     register struct hblk * h;
  591.  
  592.     bottom = (ptr_t)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
  593.     top = (ptr_t)(((long) top) & ~(ALIGNMENT-1));
  594.  
  595.     if (top == 0 || bottom == top) return;
  596.     h = HBLKPTR(bottom + HBLKSIZE);
  597.     if (top <= (ptr_t) h) {
  598.       if ((*dirty_fn)(h-1)) {
  599.         (*push_fn)(bottom, top);
  600.     }
  601.     return;
  602.     }
  603.     if ((*dirty_fn)(h-1)) {
  604.         (*push_fn)(bottom, (ptr_t)h);
  605.     }
  606.     while ((ptr_t)(h+1) <= top) {
  607.     if ((*dirty_fn)(h)) {
  608.         if ((word)(GC_mark_stack_top - GC_mark_stack)
  609.         > 3 * GC_mark_stack_size / 4) {
  610.          /* Danger of mark stack overflow */
  611.         (*push_fn)((ptr_t)h, top);
  612.         return;
  613.         } else {
  614.         (*push_fn)((ptr_t)h, (ptr_t)(h+1));
  615.         }
  616.     }
  617.     h++;
  618.     }
  619.     if ((ptr_t)h != top) {
  620.     if ((*dirty_fn)(h)) {
  621.             (*push_fn)((ptr_t)h, top);
  622.         }
  623.     }
  624.     if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) {
  625.         ABORT("unexpected mark stack overflow");
  626.     }
  627. }
  628.  
  629. # ifndef SMALL_CONFIG
  630. void GC_push_conditional(bottom, top, all)
  631. ptr_t bottom;
  632. ptr_t top;
  633. {
  634.     if (all) {
  635.       if (GC_dirty_maintained) {
  636. #    ifdef PROC_VDB
  637.         /* Pages that were never dirtied cannot contain pointers    */
  638.         GC_push_dirty(bottom, top, GC_page_was_ever_dirty, GC_push_all);
  639. #    else
  640.         GC_push_all(bottom, top);
  641. #    endif
  642.       } else {
  643.           GC_push_all(bottom, top);
  644.       }
  645.     } else {
  646.     GC_push_dirty(bottom, top, GC_page_was_dirty, GC_push_all);
  647.     }
  648. }
  649. #endif
  650.  
  651. /*
  652.  * Push a single value onto mark stack. Mark from the object pointed to by p.
  653.  * GC_push_one is normally called by GC_push_regs, and thus must be defined.
  654.  * P is considered valid even if it is an interior pointer.
  655.  * Previously marked objects are not pushed.  Hence we make progress even
  656.  * if the mark stack overflows.
  657.  */
  658. # define GC_PUSH_ONE_STACK(p) \
  659.     if ((ptr_t)(p) >= GC_least_plausible_heap_addr     \
  660.      && (ptr_t)(p) < GC_greatest_plausible_heap_addr) {    \
  661.      GC_push_one_checked(p,TRUE);    \
  662.     }
  663.  
  664. /*
  665.  * As above, but interior pointer recognition as for
  666.  * normal for heap pointers.
  667.  */
  668. # ifdef ALL_INTERIOR_POINTERS
  669. #   define AIP TRUE
  670. # else
  671. #   define AIP FALSE
  672. # endif
  673. # define GC_PUSH_ONE_HEAP(p) \
  674.     if ((ptr_t)(p) >= GC_least_plausible_heap_addr     \
  675.      && (ptr_t)(p) < GC_greatest_plausible_heap_addr) {    \
  676.      GC_push_one_checked(p,AIP);    \
  677.     }
  678.  
  679. # ifdef MSWIN32
  680.   void __cdecl GC_push_one(p)
  681. # else
  682.   void GC_push_one(p)
  683. # endif
  684. word p;
  685. {
  686.     GC_PUSH_ONE_STACK(p);
  687. }
  688.  
  689. # ifdef __STDC__
  690. #   define BASE(p) (word)GC_base((void *)(p))
  691. # else
  692. #   define BASE(p) (word)GC_base((char *)(p))
  693. # endif
  694.  
  695. /* As above, but argument passed preliminary test. */
  696. void GC_push_one_checked(p, interior_ptrs)
  697. register word p;
  698. register bool interior_ptrs;
  699. {
  700.     register word r;
  701.     register hdr * hhdr; 
  702.     register int displ;
  703.   
  704.     GET_HDR(p, hhdr);
  705.     if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
  706.         if (hhdr != 0 && interior_ptrs) {
  707.           r = BASE(p);
  708.       hhdr = HDR(r);
  709.       displ = BYTES_TO_WORDS(HBLKDISPL(r));
  710.     } else {
  711.       hhdr = 0;
  712.     }
  713.     } else {
  714.         register map_entry_type map_entry;
  715.         
  716.         displ = HBLKDISPL(p);
  717.         map_entry = MAP_ENTRY((hhdr -> hb_map), displ);
  718.         if (map_entry == OBJ_INVALID) {
  719.           if (interior_ptrs) {
  720.             r = BASE(p);
  721.         displ = BYTES_TO_WORDS(HBLKDISPL(r));
  722.         if (r == 0) hhdr = 0;
  723.           } else {
  724.             hhdr = 0;
  725.           }
  726.         } else {
  727.           displ = BYTES_TO_WORDS(displ);
  728.           displ -= map_entry;
  729.           r = (word)((word *)(HBLKPTR(p)) + displ);
  730.         }
  731.     }
  732.     /* If hhdr != 0 then r == GC_base(p), only we did it faster. */
  733.     /* displ is the word index within the block.         */
  734.     if (hhdr == 0) {
  735.         if (interior_ptrs) {
  736.         GC_add_to_black_list_stack(p);
  737.     } else {
  738.         GC_ADD_TO_BLACK_LIST_NORMAL(p);
  739.     }
  740.     } else {
  741.     if (!mark_bit_from_hdr(hhdr, displ)) {
  742.         set_mark_bit_from_hdr(hhdr, displ);
  743.         PUSH_OBJ((word *)r, hhdr, GC_mark_stack_top,
  744.                  &(GC_mark_stack[GC_mark_stack_size]));
  745.     }
  746.     }
  747. }
  748.  
  749. /*
  750.  * A version of GC_push_all that treats all interior pointers as valid
  751.  */
  752. void GC_push_all_stack(bottom, top)
  753. ptr_t bottom;
  754. ptr_t top;
  755. {
  756. # ifdef ALL_INTERIOR_POINTERS
  757.     GC_push_all(bottom, top);
  758. # else
  759.     word * b = (word *)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
  760.     word * t = (word *)(((long) top) & ~(ALIGNMENT-1));
  761.     register word *p;
  762.     register word q;
  763.     register word *lim;
  764.     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
  765.     register ptr_t least_ha = GC_least_plausible_heap_addr;
  766. #   define GC_greatest_plausible_heap_addr greatest_ha
  767. #   define GC_least_plausible_heap_addr least_ha
  768.  
  769.     if (top == 0) return;
  770.     /* check all pointers in range and put in push if they appear */
  771.     /* to be valid.                          */
  772.       lim = t - 1 /* longword */;
  773.       for (p = b; p <= lim; p = (word *)(((char *)p) + ALIGNMENT)) {
  774.     q = *p;
  775.     GC_PUSH_ONE_STACK(q);
  776.       }
  777. #   undef GC_greatest_plausible_heap_addr
  778. #   undef GC_least_plausible_heap_addr
  779. # endif
  780. }
  781.  
  782. #ifndef SMALL_CONFIG
  783. /* Push all objects reachable from marked objects in the given block */
  784. /* of size 1 objects.                             */
  785. void GC_push_marked1(h, hhdr)
  786. struct hblk *h;
  787. register hdr * hhdr;
  788. {
  789.     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
  790.     register word *p;
  791.     word *plim;
  792.     register int i;
  793.     register word q;
  794.     register word mark_word;
  795.     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
  796.     register ptr_t least_ha = GC_least_plausible_heap_addr;
  797. #   define GC_greatest_plausible_heap_addr greatest_ha
  798. #   define GC_least_plausible_heap_addr least_ha
  799.     
  800.     p = (word *)(h->hb_body);
  801.     plim = (word *)(((word)h) + HBLKSIZE);
  802.  
  803.     /* go through all words in block */
  804.     while( p < plim )  {
  805.         mark_word = *mark_word_addr++;
  806.         i = 0;
  807.         while(mark_word != 0) {
  808.           if (mark_word & 1) {
  809.               q = p[i];
  810.               GC_PUSH_ONE_HEAP(q);
  811.           }
  812.           i++;
  813.           mark_word >>= 1;
  814.         }
  815.         p += WORDSZ;
  816.     }
  817. #   undef GC_greatest_plausible_heap_addr
  818. #   undef GC_least_plausible_heap_addr        
  819. }
  820.  
  821.  
  822. /* Push all objects reachable from marked objects in the given block */
  823. /* of size 2 objects.                             */
  824. void GC_push_marked2(h, hhdr)
  825. struct hblk *h;
  826. register hdr * hhdr;
  827. {
  828.     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
  829.     register word *p;
  830.     word *plim;
  831.     register int i;
  832.     register word q;
  833.     register word mark_word;
  834.     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
  835.     register ptr_t least_ha = GC_least_plausible_heap_addr;
  836. #   define GC_greatest_plausible_heap_addr greatest_ha
  837. #   define GC_least_plausible_heap_addr least_ha
  838.     
  839.     p = (word *)(h->hb_body);
  840.     plim = (word *)(((word)h) + HBLKSIZE);
  841.  
  842.     /* go through all words in block */
  843.     while( p < plim )  {
  844.         mark_word = *mark_word_addr++;
  845.         i = 0;
  846.         while(mark_word != 0) {
  847.           if (mark_word & 1) {
  848.               q = p[i];
  849.               GC_PUSH_ONE_HEAP(q);
  850.               q = p[i+1];
  851.               GC_PUSH_ONE_HEAP(q);
  852.           }
  853.           i += 2;
  854.           mark_word >>= 2;
  855.         }
  856.         p += WORDSZ;
  857.     }
  858. #   undef GC_greatest_plausible_heap_addr
  859. #   undef GC_least_plausible_heap_addr        
  860. }
  861.  
  862. /* Push all objects reachable from marked objects in the given block */
  863. /* of size 4 objects.                             */
  864. /* There is a risk of mark stack overflow here.  But we handle that. */
  865. /* And only unmarked objects get pushed, so it's not very likely.    */
  866. void GC_push_marked4(h, hhdr)
  867. struct hblk *h;
  868. register hdr * hhdr;
  869. {
  870.     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
  871.     register word *p;
  872.     word *plim;
  873.     register int i;
  874.     register word q;
  875.     register word mark_word;
  876.     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
  877.     register ptr_t least_ha = GC_least_plausible_heap_addr;
  878. #   define GC_greatest_plausible_heap_addr greatest_ha
  879. #   define GC_least_plausible_heap_addr least_ha
  880.     
  881.     p = (word *)(h->hb_body);
  882.     plim = (word *)(((word)h) + HBLKSIZE);
  883.  
  884.     /* go through all words in block */
  885.     while( p < plim )  {
  886.         mark_word = *mark_word_addr++;
  887.         i = 0;
  888.         while(mark_word != 0) {
  889.           if (mark_word & 1) {
  890.               q = p[i];
  891.               GC_PUSH_ONE_HEAP(q);
  892.               q = p[i+1];
  893.               GC_PUSH_ONE_HEAP(q);
  894.               q = p[i+2];
  895.               GC_PUSH_ONE_HEAP(q);
  896.               q = p[i+3];
  897.               GC_PUSH_ONE_HEAP(q);
  898.           }
  899.           i += 4;
  900.           mark_word >>= 4;
  901.         }
  902.         p += WORDSZ;
  903.     }
  904. #   undef GC_greatest_plausible_heap_addr
  905. #   undef GC_least_plausible_heap_addr        
  906. }
  907.  
  908. #endif /* SMALL_CONFIG */
  909.  
  910. /* Push all objects reachable from marked objects in the given block */
  911. void GC_push_marked(h, hhdr)
  912. struct hblk *h;
  913. register hdr * hhdr;
  914. {
  915.     register int sz = hhdr -> hb_sz;
  916.     register word * p;
  917.     register int word_no;
  918.     register word * lim;
  919.     register mse * GC_mark_stack_top_reg;
  920.     register mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]);
  921.     
  922.     /* Some quick shortcuts: */
  923.         if (hhdr -> hb_obj_kind == PTRFREE) return;
  924.         if (GC_block_empty(hhdr)/* nothing marked */) return;
  925. #   ifdef GATHERSTATS
  926.         GC_n_rescuing_pages++;
  927. #   endif
  928.     GC_objects_are_marked = TRUE;
  929.     if (sz > MAXOBJSZ) {
  930.         lim = (word *)(h + 1);
  931.     } else {
  932.         lim = (word *)(h + 1) - sz;
  933.     }
  934.     
  935.     switch(sz) {
  936. #   ifndef SMALL_CONFIG    
  937.      case 1:
  938.        GC_push_marked1(h, hhdr);
  939.        break;
  940.      case 2:
  941.        GC_push_marked2(h, hhdr);
  942.        break;
  943.      case 4:
  944.        GC_push_marked4(h, hhdr);
  945.        break;
  946. #   endif       
  947.      default:
  948.       GC_mark_stack_top_reg = GC_mark_stack_top;
  949.       for (p = (word *)h + HDR_WORDS, word_no = HDR_WORDS; p <= lim;
  950.          p += sz, word_no += sz) {
  951.          /* This needs manual optimization: */
  952.          if (mark_bit_from_hdr(hhdr, word_no)) {
  953.            /* Mark from fields inside the object */
  954.              PUSH_OBJ((word *)p, hhdr, GC_mark_stack_top_reg, mark_stack_limit);
  955. #         ifdef GATHERSTATS
  956.         /* Subtract this object from total, since it was    */
  957.         /* added in twice.                    */
  958.         GC_composite_in_use -= sz;
  959. #         endif
  960.          }
  961.       }
  962.       GC_mark_stack_top = GC_mark_stack_top_reg;
  963.     }
  964. }
  965.  
  966. #ifndef SMALL_CONFIG
  967. /* Test whether any page in the given block is dirty    */
  968. bool GC_block_was_dirty(h, hhdr)
  969. struct hblk *h;
  970. register hdr * hhdr;
  971. {
  972.     register int sz = hhdr -> hb_sz;
  973.     
  974.     if (sz < MAXOBJSZ) {
  975.          return(GC_page_was_dirty(h));
  976.     } else {
  977.          register ptr_t p = (ptr_t)h;
  978.          sz += HDR_WORDS;
  979.          sz = WORDS_TO_BYTES(sz);
  980.          while (p < (ptr_t)h + sz) {
  981.              if (GC_page_was_dirty((struct hblk *)p)) return(TRUE);
  982.              p += HBLKSIZE;
  983.          }
  984.          return(FALSE);
  985.     }
  986. }
  987. #endif /* SMALL_CONFIG */
  988.  
  989. /* Similar to GC_push_next_marked, but return address of next block    */
  990. struct hblk * GC_push_next_marked(h)
  991. struct hblk *h;
  992. {
  993.     register hdr * hhdr;
  994.     
  995.     h = GC_next_block(h);
  996.     if (h == 0) return(0);
  997.     hhdr = HDR(h);
  998.     GC_push_marked(h, hhdr);
  999.     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
  1000. }
  1001.  
  1002. #ifndef SMALL_CONFIG
  1003. /* Identical to above, but mark only from dirty pages    */
  1004. struct hblk * GC_push_next_marked_dirty(h)
  1005. struct hblk *h;
  1006. {
  1007.     register hdr * hhdr = HDR(h);
  1008.     
  1009.     if (!GC_dirty_maintained) { ABORT("dirty bits not set up"); }
  1010.     for (;;) {
  1011.         h = GC_next_block(h);
  1012.         if (h == 0) return(0);
  1013.         hhdr = HDR(h);
  1014. #    ifdef STUBBORN_ALLOC
  1015.           if (hhdr -> hb_obj_kind == STUBBORN) {
  1016.             if (GC_page_was_changed(h) && GC_block_was_dirty(h, hhdr)) {
  1017.                 break;
  1018.             }
  1019.           } else {
  1020.             if (GC_block_was_dirty(h, hhdr)) break;
  1021.           }
  1022. #    else
  1023.       if (GC_block_was_dirty(h, hhdr)) break;
  1024. #    endif
  1025.         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
  1026.     }
  1027.     GC_push_marked(h, hhdr);
  1028.     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
  1029. }
  1030. #endif
  1031.  
  1032. /* Similar to above, but for uncollectable pages.  Needed since we    */
  1033. /* do not clear marks for such pages, even for full collections.    */
  1034. struct hblk * GC_push_next_marked_uncollectable(h)
  1035. struct hblk *h;
  1036. {
  1037.     register hdr * hhdr = HDR(h);
  1038.     
  1039.     for (;;) {
  1040.         h = GC_next_block(h);
  1041.         if (h == 0) return(0);
  1042.         hhdr = HDR(h);
  1043.     if (hhdr -> hb_obj_kind == UNCOLLECTABLE) break;
  1044.         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
  1045.     }
  1046.     GC_push_marked(h, hhdr);
  1047.     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
  1048. }
  1049.  
  1050.  
  1051.